4.2 Численные методы безусловной минимизации
функции многих переменных
Ставится задача минимизации функции
)()(
n21
,...xx,xff x
в некоторой замкнутой области. Пусть
)(
n21
a,...,a,aa
точка минимума
)(xf
. Будем говорить, что с
точностью до
точка x может быть взята в качестве
приближенного значения точки минимума, если
|||| xa
, где
n
1i
2
ii
xa|||| xa
или
|||| xa
=
.
Для геометрической иллюстрации методов будем
использовать функцию двух переменных. Напомним, что
линиями уровня функции Z=f(x,y) называют множество
точек
yx,
, удовлетворяющих уравнению f(x,y)=c. Меняя c,
мы получаем различные линии уровня функции f(x,y).
Геометрически линия уровня – это проекция на плоскость
ХОУ линии пересечения Z=f(x,y) и плоскости Z=c. Имея
множество линий уровня, мы получаем представление о
поведении Z=f
(x,y), говорят о рельефе функции Z=f
(x,y).
4.2.1 Методы многомерного прямого поиска
Суть методов многомерного прямого поиска,
изложенных ниже, в том, что выбирают некоторую точку
)...,,(
)0()0()0(
n1
xxx
и допустимое направление поиска
d
.
Затем, отправляясь от точки
)0(
x
в направлении
d
,
минимизируют функцию одного переменного λ:
)λ( dx f
,
изложенными выше методами.
Найдя
)0(
λ
, при котором
)λ(
(0)
dx f
получает
минимальное значение, мы тем самым нашли точку
dxx
)0()0()1(
λ
, в которой значение f, вообще говоря,
меньше чем в точке
)0(
x
. Далее, отправляясь от
)1(
x
в
некотором новом направлении
1
d
, получаем некоторую
точку
)2(
x
, в которой значение f вообще говоря, меньше чем
в
)1(
x
и т.д. Возникают вопросы: 1) Как целесообразнее
выбирать
i
d
? 2) Сходится ли последовательность
)0(
x
,
)1(
x
, .
. .? 3) Как оценить погрешность?
4.2.2 Метод циклического покоординатного спуска
Опишем алгоритм одного из таких методов, выбирая в
качестве направлений поиска координатные векторы
nn2211
ldld,ld ,...,
, т.е.
ii
ld
- вектор, все компоненты
которого, за исключением i равны нулю.
Тогда
)0(
)0()0()0()0()0(
)0(
,...,,λ,,...,,λ
n
1i
i
-1i21
i
xxxxxx
lx
,
(0)(0)(0)(0)(0)(0))0(
λ)λ(
n1ii1i21i
x,...,x,x,x,...,x,xff lx
и,
следовательно, при минимизации функции
)λ(
)0(
i
f lx
, речь
идет о минимизации функции одной переменной
i
i
i
xx λ
(0)
, при фиксированных остальных переменных.
Выберем начальную точку
)0(
x
1
y
, направление
11
ld
и, минимизируя
)λ(
11
f ly
, найдем, что минимум этой
функции достигается при
1
λ
, в точке
)0()0()0(
,...,,λλ
n2111112
xxxlyy
. Положим
1112
lλ yy
,
выберем направление
2
l
и, минимизируя
)λ(
22
f ly
найдем,
что минимум этой функции достигается при
2
λ
в точке
(0))0(
)0(
)0(
,...,,λ,λλ
n32
2
1
12223
xxxxlyy
.
После n шагов найдем
nn2211nnn1n
xxx λ,...,λ,λλ
(0))0()0(
lyy
.
Положим
1n
y
)1(
x
и тем самым завершим один цикл
покоординатного спуска.
Отправляясь от
)1(
x
, как от начальной точки, можем
найти
)2(
x
и т.д.
Процесс завершить, если
||||
)()( k1k
xx
,
где
− требуемая точность,
n
1i
i
1k
i
k1k
xx
2
)()(
)()(
k
||x||x
или
||x||x
)()( k1k
=
)(|max
)()(
n1,i|xx
k
i
1k
i
.
Проиллюстрируем метод с помощью функции двух
переменных (рисунок 4.4).
Рисунок 4.4 – Метод циклического покоординатного
спуска
Двигаясь от точки
1
y
)0(
x
параллельно оси ОХ
1
, мы
переходим от линий уровня с большим значением
cx,xf
21
к меньшим. Точка
2
y
, в которой мы коснемся
некоторой линии уровня, является точкой минимума
функции
)(
)0(
2
1
x,xf
в направлении, параллельном оси ОХ
1
.
Двигаясь от точки
2
y
параллельно оси ОХ
2
, мы, переходя от
линий уровня с большим "c" к линиям уровня с меньшим "c",
достигнем минимального значения в точке
3
y
- точке
касания некоторой линии уровня. В точке
3
y
завершается
цикл покоординатного спуска и получаем
)1(
x
=
3
y
.
Отправляясь от
)1(
x
, как от начальной точки, можем
найти
)2(
x
и т.д. Остается указать условия сходимости
последовательности
)0(
x
,
)1(
x
, ... и указать оценку
погрешности.
1
y
)0(
x
)2(
x
2
y
)2(
3
xy
х
2
х
1
Для сходимости метода циклического покоординатного
спуска достаточно следующих требований:
1) минимум
)(xf
вдоль любого направления
единственен;
2) последовательность точек
)(
...,,
)1(
,
)0( k
xxx
принадлежит
некоторому замкнутому ограниченному подмножеству
области
D
.
Что касается погрешности, то ее можно определить по
формуле:
||||||||
)()()( k1k1k
xxxa
.
ЗАМЕЧАНИЕ. Если функция f не является
дифференцируемой в некоторых точках, то метод может
остановиться в неоптимальной точке (рисунок 4.5).
Рисунок 4.5 – Неоптимальная точка
Ясно, что поиск вдоль любой координатной оси в точке
)2(
x
не приводит к улучшению целевой функции. Это
вызвано наличием так называемого оврага, то есть точки
недифференцируемой функции
)(xf
. Разрешить эту
ситуацию можно используя, например, метод Хука−Дживса.
4.2.3 Метод Хука-Дживса
Метод Хука-Дживса осуществляет два типа поиска:
исследующий поиск и поиск по образцу. Выбрав начальную
точку
1
x
методом циклического покоординатного спуска,
находим точку
2
x
, т.е. осуществляем исследующий поиск.
Если
||||
12
xx
, то точка минимума найдена, иначе
осуществляем поиск по образцу в направлении
dxx
12
, что
приводит нас в некоторую точку
y
. Приняв
y
за
1
x
вновь
x
y
)1(
x
)2(
x
проводим исследующий поиск и т.д. Сходимость метода
Хука-Дживса обеспечена при тех же условиях, что и
покоординатного спуска. Иллюстрация метода на рисунке
4.6 .
Рисунок 4.6 – Метод Хука-Дживса
4.2.4 Метод наискорейшего спуска
Известно, что направлением наибольшего возрастания
функции f в точке
)0(
x
является направление, задаваемое
вектором
)(
)0(
xfgrad
, а
))((
)0(
xfgrad
задает направление
наибольшего убывания функции f в точке
)0(
x
. Учитывая это,
следует осуществлять линейный поиск не в направлении
осей координат, а в направлении
fgrad
.
Рассмотрим алгоритм метода.
1. Выбираем
1, i
i
x
.
2. Если
||)(||
i
fgrad x
, то
i
x
- искомая точка.
3. В противном случае положим
)(
ii
fgradd x
и
решив задачу о минимуме
ii
df λx
, найдем λ
i
>0.
4. Найдем
iii1i
dλ
xx
и переходим к пункту 2,
положив i=i+1.
Сходимость метода обеспечена, если f непрерывно
дифференцируема, а генерируемая последовательность,
принадлежит замкнутому ограниченному множеству.
2
x
y
1
x
1
x
2
x
y
x
Недостатком метода наискорейшего спуска является
зачастую медленная сходимость в окрестности
стационарной точки. Это очевидно, например, в тех случаях,
когда линии уровня вытянуты в окрестности оптимальной
точки. О функциях, поверхности уровня которых сильно
вытянуты, говорят, что она имеет "овражный'' характер.
Геометрически медленная сходимость объясняется так:
спустившись на "дно оврага'' мы, двигаясь в направлении (
fgrad
), будем переходить с одного склона оврага на
другой, то есть зигзагообразно продвигаться к точке
минимума (рисунок 4.7).
Рисунок 4.7 – Овражная функция
Что касается степени "овражности", то ее можно
охарактеризовать с помощью минимального (λ
min
) и
максимального (λ
max
) собственных чисел матрицы Гессе −
ji
2
xx
f
(
;n,1i
n,1j
). Чем меньше λ
min
/ λ
max
, тем больше
овражность. Более предпочтительными в таких случаях
являются методы Ньютона и сопряженных направлений.
Коротко суть первого из них состоит в том, что функция
)(xf
аппроксимируется (с помощью формулы Тейлора)
многочленами второй степени, для которых находятся точки
минимума. Последовательность таких точек приводит при
определенных условиях к искомой точке минимума
)(xf
.
Неудобством метода является необходимость
многократного обращения матрицы Гессе.
Второй из методов для получения очередной точки
требует проведения последовательной минимизации по
каждому из n, специальным образом построенных
направлений, которые называют сопряженными
направлениями. Для квадратичной функции минимизация
вдоль "n" таких направлений позволяет "точно" достичь
точки минимума, а следовательно можно ожидать хороших
результатов и для достаточно гладких функций. Подробнее
с этими методами можно познакомиться в [4].